package com.future;

import com.future.util.TreeNode;

/**
 * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
 * <p>
 * 叶子节点 是指没有子节点的节点。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/path-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_hasPathSum_112 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5,
                new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2)), null),
                new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))));
        //root = new TreeNode();
        int targetSum = 0;
        // 这个用例不过，找不到原因
        System.out.println(hasPathSum(root, targetSum));
        // 这个过了
        System.out.println(hasPathSum_v2(root, targetSum));
    }

    public static boolean isSum = false;

    public static boolean hasPathSum_v2(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        isSum = false;
        process(root, 0, targetSum);
        return isSum;
    }


    public static void process(TreeNode root, int preSum, int targetSum) {
        if (root.left == null && root.right == null) {
            if (preSum + root.val == targetSum) {
                isSum = true;
            }
        }
        preSum += root.val;
        if (root.left != null) {
            process(root.left, preSum, targetSum);
        }
        if (root.right != null) {
            process(root.right, preSum, targetSum);
        }
    }


    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return BST(root, targetSum);
    }

    public static boolean BST(TreeNode root, int targetSum) {
        if (root == null && targetSum == 0) {
            return true;
        }
        boolean left = BST(root.left, targetSum - root.val);
        boolean right = BST(root.right, targetSum - root.val);
        return left || right;
    }

}
